{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "",
   "id": "216f3e9d0f5dc0db"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 2.排序",
   "id": "1e41e5e35d79a221"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### （1）冒泡排序",
   "id": "59eca20e2e4ab91"
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-02-25T06:12:27.618825Z",
     "start_time": "2025-02-25T06:12:27.595286Z"
    }
   },
   "source": [
    "def bubble_sort(items):\n",
    "    num=len(items)\n",
    "    for i in range(num):    #i初始值为0\n",
    "        q=num-i-1\n",
    "        for j in range(q):     #每轮对比次数\n",
    "            if items[j]>items[j+1]:\n",
    "                items[j],items[j+1]=items[j+1],items[j]\n",
    "        return items\n",
    "\n",
    "list=[4,7,2,9,1,8,6,3,5]\n",
    "print(bubble_sort(list))"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 2, 7, 1, 8, 6, 3, 5, 9]\n"
     ]
    }
   ],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## （2）选择排序",
   "id": "8c255e4aabf7ffc1"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-25T07:18:08.842114Z",
     "start_time": "2025-02-25T07:18:08.816468Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def select_sort(items,comp=lambda x,y:x<y):\n",
    "    items=items[:]                  \n",
    "    for i in range (len(items)-1):\n",
    "        min_index=i\n",
    "        for j in range (i+1,len(items)):\n",
    "            if comp(items[j],items[min_index]):\n",
    "                min_index=j\n",
    "        items[i],items[min_index]=items[min_index],items[i]\n",
    "        print(f'遍历第{i+1}次',f'i的索引是{i}',f'最小的元素索引是{min_index}')\n",
    "        print(\" \")\n",
    "    return items\n",
    "\n",
    "items=[4,7,2,9,1,8,6,3,5]\n",
    "print(select_sort(items=items))"
   ],
   "id": "c3d1eea1e10eafdc",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "遍历第1次 i的索引是0 最小的元素索引是4\n",
      " \n",
      "遍历第2次 i的索引是1 最小的元素索引是2\n",
      " \n",
      "遍历第3次 i的索引是2 最小的元素索引是7\n",
      " \n",
      "遍历第4次 i的索引是3 最小的元素索引是4\n",
      " \n",
      "遍历第5次 i的索引是4 最小的元素索引是8\n",
      " \n",
      "遍历第6次 i的索引是5 最小的元素索引是6\n",
      " \n",
      "遍历第7次 i的索引是6 最小的元素索引是7\n",
      " \n",
      "遍历第8次 i的索引是7 最小的元素索引是7\n",
      " \n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "execution_count": 3
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## (3)插入排序[8,5,2,9,5,6,3]\n",
   "id": "175a48ffc52e311c"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-02-25T07:22:12.491230Z",
     "start_time": "2025-02-25T07:22:12.446797Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def insertionSort(array):\n",
    "    for idx in range(1,len(array)):\n",
    "        j=idx\n",
    "        while j>0 and array[j]<array[j-1]:\n",
    "            (array[j-1],array[j])=(array[j],array[j-1])\n",
    "            j-=1\n",
    "    return array\n",
    "\n",
    "array=[8,5,2,9,5,6,3]\n",
    "print(insertionSort(array))"
   ],
   "id": "c8824174f48f54cd",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 5, 6, 8, 9]\n"
     ]
    }
   ],
   "execution_count": 4
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
